package twobranchTree.postorderTraversal;

import java.util.ArrayList;
import java.util.Collections;
import java.util.LinkedList;
import java.util.List;

import twobranchTree.preorderTraversal.TreeNode;

/**
 * @Date 2020/2/11
 * @author 王光浩 
 * @Description 给出一颗二叉树，对它进行后序遍历。
 * @Thinking 使用Morris遍历法进行。方法如下：将二叉树进行根——右节点——左节点的遍历方法，然后最后将结果进行反转即可。（太笨了自己）
 */
public class MyMethodTwo {
	public List<Integer> postorderTraversal(TreeNode root) {
		List<Integer> result=new ArrayList<Integer>();
		LinkedList<Integer> real=new LinkedList<Integer>();
		TreeNode node=root;
		while(node!=null) {
			if(node.right==null) {  //节点没有右节点（不需要遍历右子树，直接进入左子树）
				result.add(node.val);
				node=node.left;
			}
			else {  //存在右节点，需要判断是否是右子树遍历完毕需要遍历左子树，还是没有遍历右子树
				TreeNode postorder=node.right;
				while(postorder.left!=null && postorder.left!=node) {
					postorder=postorder.left;
				}
				if(postorder.left==null) {  //该右子树没有遍历过
					result.add(node.val);
					postorder.left=node; //最后一个节点与根根节点形成环
					node=node.right;
				}
				else {
					node=node.left;
				}
			}
		}
		for(Integer e:result) {
			real.addFirst(e);
		}
		return real;
	}
	/**
	 * 将二叉树进行反转，然后按照Morris前序遍历的方式进行遍历，最后将遍历的结果进行翻转即可。
	 * @param root
	 * @return
	 */
	public List<Integer> postorderTraversal1(TreeNode root) {
		List<Integer> ret = new ArrayList<Integer>();
		TreeNode node = root;
		while (node != null) {
			if (node.right == null) {
				ret.add(node.val);
				node = node.left;
			} else {
				TreeNode next = node.right;
				while (next.left != null && next.left != node)
					next = next.left;
				if (next.left == null) {
					ret.add(node.val);
					next.left = node;
					node = node.right;
				} else {
					next.left = null;
					node = node.left;
				}
			}
		}
		Collections.reverse(ret);
		return ret;
	}
}
